/**
 * Created by clq on 2019/3/5.
 */
public class FastSort {
    public static void main(String[] args) {
        Comparable arr[] = {1,2,3,4,5,6,7,8,1,1,1,9,10};
        sort(arr, 0, arr.length-1);
        for (Comparable i:arr) {
            System.out.println(i);
        }
    }

    public static void sort(Comparable arr[], int lo, int hi) {
        if(lo<hi) {
            int j = partition(arr, lo, hi);
            sort(arr, lo, j-1);
            sort(arr, j+1, hi);
        }
    }

    public static int partition(Comparable arr[], int lo, int hi) {
        int i = lo;
        int j = hi+1;
        Comparable v = arr[lo];

        while (true) {
            while (less(v, arr[++i])){if(i==hi) break;}
            while (less(arr[--j], v)){if(j==lo) break;}
            if(i>=j) {
                break;
            }
            swap(arr, i, j);
            for (Comparable a:arr
                 ) {
                System.out.print(a+",");
            }
            System.out.println();
        }
        swap(arr, lo, j);
        for (Comparable a:arr
                ) {
            System.out.print(a+",");
        }
        System.out.println();
        return j;
    }

    public static void swap(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void swim(int k) {
      /*  while (2*k<=n) {

        }*/
    }

    public static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b)<0 ? true:false;
    }
}
